import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author abin
 * @date 2024/12/14 15:12
 * @description 两阶段终止模式：发送终止指令+响应终止指令(interrupt()方法和终止标识变量)。
 * 优雅的线程终止
 * 1.自定义terminated标志位 推荐
 * 2.Thread.currentThread().interrupt();这种方式不可控，没有办法保证第三方类库正确处理了线程的中断异常，
 * <p>
 * 线程池优雅终止
 * 1.shutdown，保守的关闭线程池的方法。线程池执行 shutdown() 后，就会拒绝接收新的任务，
 * 但是会等待线程池中正在执行的任务和已经进入阻塞队列的任务都执行完之后才最终关闭线程池。
 * 2.shutdownNow，会拒绝接收新的任务，同时还会中断线程池中正在执行的任务，已经进入阻塞队列的任务也被剥夺了执行的机会
 * 这些任务会作为方法的返回值返回。任务保存起来，后续以补偿的方式重新执行
 */

public class ThreadTermination {
    //线程终止标志位
    volatile boolean terminated = false;
    boolean started = false;
    //采集线程
    Thread rptThread;

    //启动采集功能
    synchronized void start() {
        //不允许同时启动多个采集线程
        if (started) {
            return;
        }
        started = true;
        terminated = false;
        rptThread = new Thread(() -> {
            while (!terminated) {
                //省略采集、回传实现
                report();
                //每隔两秒钟采集、回传一次数据
                try {
                    Thread.sleep(2000);
                } catch (InterruptedException e) {
                    //重新设置线程中断状态，interrupt会将线程休眠状态转为runnable状态
                    //Thread.currentThread().interrupt();
                    System.out.println("线程被中断，重新设置中断状态");
                }
            }
            //执行到此处说明线程马上终止
            started = false;
        });
        rptThread.start();
    }

    private void report() {
        System.out.println("采集并回传数据");
    }

    //终止采集功能
    synchronized void stop() {
        //设置中断标志位
        terminated = true;
        //中断线程rptThread
        rptThread.interrupt();
    }

    public static void main(String[] args) {
        int[][] array = {
                {0, 1},
                {0, 2},
                {2, 3},
                {2, 4}
        };

        int[][] array1 = {
                {0, 1},
                {0, 2},
                {0, 3},
                {2, 7},
                {1, 4},
                {4, 5},
                {4, 6}
        };


        int[] ints = maxTargetNodes(array, array1);
//        for (int i : ints) {
//            System.out.print(i + " ");
//        }

        System.out.println(minCostClimbingStairs(new int[]{10,15,20}));
    }

    public static int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n+1];

        dp[0] = cost[0];
        dp[1] = cost[1];
        for(int i=2; i<n; i++){
            dp[i] = Math.min(dp[i-2]+cost[i], dp[i-1]+cost[i]);
        }
        dp[n] = Math.min(dp[n-2], dp[n-1]);
        return dp[n];
    }

    public static int[] maxTargetNodes(int[][] edges1, int[][] edges2) {
        int n2 = edges2.length + 1;
        List<List<Integer>> l2 = new ArrayList<>(n2);
        for (int i = 0; i < n2; i++) {
            l2.add(new ArrayList<>());
        }
        for (int[] edge : edges2) {
            l2.get(edge[0]).add(edge[1]);
            l2.get(edge[1]).add(edge[0]);
        }
        int[] dp2 = new int[n2];
        int max2 = 0;
        for (int i = 0; i < l2.size(); i++) {
            dp2[i] = dfs1(l2, l2.size(), i, -1, 1, 0);
            max2 = Math.max(max2, dp2[i]);
        }


        int n1 = edges1.length + 1;
        List<List<Integer>> l1 = new ArrayList<>(n1);
        for (int i = 0; i < n1; i++) {
            l1.add(new ArrayList<>());
        }
        for (int[] edge : edges1) {
            l1.get(edge[0]).add(edge[1]);
            l1.get(edge[1]).add(edge[0]);
        }
        int[] dp1 = new int[n1];
        for (int i = 0; i < l1.size(); i++) {
            dp1[i] = dfs1(l1, l1.size(), i, -1, 0, 1) + max2;
        }

        return dp1;
    }

    private static int dfs1(List<List<Integer>> list, int size, int node, int parent, int k, int res) {
        if (k >= size) {
            return res;
        }
        k++;
        for (int cur : list.get(node)) {
            if (cur == parent) {
                continue;
            }
            if (k % 2 == 0) {
                res ++;
            }
            res = dfs1(list, size, cur, node, k, res);
        }
        return res;
    }


    public static int[] maxTargetNodes(int[][] edges1, int[][] edges2, int k) {
        if (k == 0) {
            int[] ans = new int[edges1.length + 1];
            for (int i = 0; i < ans.length; i++) {
                ans[i] = 1;
            }
            return ans;
        }
        // 构建edges1邻接表
        int n1 = edges1.length + 1;
        List<List<Integer>> l1 = new ArrayList<>(n1);
        for (int i = 0; i < n1; i++) {
            l1.add(new ArrayList<>());
        }
        for (int[] edge : edges1) {
            l1.get(edge[0]).add(edge[1]);
            l1.get(edge[1]).add(edge[0]);
        }

        int[] dp1 = new int[n1];
        for (int i = 0; i < l1.size(); i++) {
            dp1[i] = dfs(l1, i, -1, k, 1);
        }


        // 构建edges2邻接表  5 3 5 4 4
        int n2 = edges2.length + 1;
        List<List<Integer>> l2 = new ArrayList<>(n2);
        for (int i = 0; i < n2; i++) {
            l2.add(new ArrayList<>());
        }
        for (int[] edge : edges2) {
            l2.get(edge[0]).add(edge[1]);
            l2.get(edge[1]).add(edge[0]);
        }
        int[] dp2 = new int[n2];
        for (int i = 0; i < l2.size(); i++) {
            dp2[i] = dfs(l2, i, -1, k - 1, 0);
        }

        int ans2 = 0;
        for (int i = 0; i < n2; i++) {
            ans2 = Math.max(ans2, dp2[i]);
        }

        int[] ans = new int[n1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = dp1[i] + ans2 + 1;
        }

        return ans;
    }

    private static int dfs(List<List<Integer>> l, int node, int parent, int k, int res) {
        if (k == 0) {
            return res;
        }
        k--;
        for (int cur : l.get(node)) {
            if (cur == parent) {
                continue;
            }
            res++;
            res = dfs(l, cur, node, k, res);
        }
        return res;
    }

    public int snakesAndLadders(int[][] board) {
        // 行数
        int n = board.length;
        boolean[] visted = new boolean[n * n + 1];
        // 存放坐标
        Queue<int[]> queue = new LinkedList<>();
        queue.offer( new int[]{1, 0});

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for ( int i = 1; i <= 6; i++) {
                int next = cur[0] + i;
                if (next > n*n) {
                    break;
                }
                int[] nextPos = getPos(next, n);
                if ( board[nextPos[0]][nextPos[1]] >0) {
                    next = board[nextPos[0]][nextPos[1]];
                }
                if (next == n*n) {
                    return cur[1] + 1;
                }
                if (!visted[next]) {
                    visted[next] = true;
                    queue.offer( new int[]{next, cur[1] + 1});
                }
            }
        }

        return -1;
    }

    private int[] getPos(int id, int n) {
        // 行数
        int row = (id - 1) / n;
        // 列数
        int col = (id - 1 )% n;
        if(row % 2 == 1) {
            col = n - 1- col;
        }
        return new int[]{n-1-row, col};
    }
}
